# date:20210328
from typing import List

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        if not intervals:
            return [newInterval]
        if not newInterval:
            return intervals
        if newInterval[0] > intervals[-1][1]:
            intervals.append(newInterval)
            return intervals
        if newInterval[1] < intervals[0][0]:
            return [newInterval] + intervals
        result = []
        min1 = 99999999
        max1 = -99999999
        flag = 0
        for interval in intervals:
            if not ((newInterval[0] > interval[1]) or (interval[0] > newInterval[1])):
                min1 = min(interval[0], min1, newInterval[1])
                max1 = max(interval[1], max1, newInterval[1])
                flag = 1
            else:
                if flag:
                    result.append([min1, max1])
                result.append(interval)
                flag = 0
        if flag:
            result.append([min1, max1])
        return result


intervals = [[1,3],[6,9]]
newInterval = [2,5]
model = Solution().insert(intervals, newInterval)
print(model)


intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]]
newInterval = [4,8]
model = Solution().insert(intervals, newInterval)
print(model)


intervals = []
newInterval = [5,7]
model = Solution().insert(intervals, newInterval)
print(model)


intervals = [[1,5]]
newInterval = [2,3]
model = Solution().insert(intervals, newInterval)
print(model)


intervals = [[1,5]]
newInterval = [6,8]
model = Solution().insert(intervals, newInterval)
print(model)